# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/16 16:30 
"""

"""
链表：不需要用地址连续的存储单元实现
"""


class Node:
    """
    data:节点保存的数据
    _next:保存下一个节点对象
    """

    def __init__(self, data, pnext=None):
        self.data = data
        self._next = pnext

    def __repr__(self):
        """
        用来定义node的字段输出
        print输出data
        """
        return str(self.data)


class ChainTable(object):
    def __init__(self):
        self.head = None
        self.length = 0

    def isEmpty(self):
        """
        定义链表操作类，如链表头属性，链表长度属性length.
        isEmpty判断链表是否为空
        """
        return self.length == 0

    def append(self, dataOrNode):
        """
        使用append在链表的末尾增加一个节点
        """
        item = None
        if isinstance(dataOrNode, Node):
            item = dataOrNode
        else:
            item = Node(dataOrNode)

        if not self.head:
            self.head = item
            self.length += 1

        else:
            node = self.head
            while node._next:
                node = node._next
            node._next = item
            self.length += 1

    def delete(self, index_var):
        """
        删除一个节点
        """
        if self.isEmpty():
            print('this chain is empty.')
            return None

        if index_var < 0 or index_var > self.length:
            print('error: out of index')

        if index_var == 0:
            self.head = self.head._next  # self.head._next???
            self.length -= 1
            return None

        j = 0
        node = self.head
        prev = self.head
        while node._next and j < index_var:
            prev = node
            node = node._next
            j += 1

        if j == index_var:
            prev._next = node._next
            self.length -= 1

    def update(self, index, data):
        """
        修改一个节点
        """
        if self.isEmpty() or index < 0 or index > self.length:
            print('error: out of index')
            return None

        j = 0
        node = self.head
        while node._next and j < index:
            node = node._next
            j += 1

        if j == index:
            node.data = data

    def getItem(self, index):
        """
        查找一个节点
        """
        if self.isEmpty() or index < 0 or index > self.length:
            print('error: out of index')
            return None

        j = 0
        node = self.head
        while node._next and j < index:
            node = node._next
            j += 1
        return node.data

    def getIndex(self, data):
        """
        查找一个节点的索引
        """
        j = 0
        if self.isEmpty():
            print('this chain is empty')
            return None
        node = self.head
        while node:
            if node.data == data:
                return j
            node = node._next
            j += 1
        if j == self.length:
            print('not found!')
            return None

    def insert(self, index, dataOrNode):
        """
        插入一个新的节点
        """
        if self.isEmpty():
            print('this chain table is empty')
            return
        if index < 0 or index >= self.length:
            print('error:out of length')
            return

        item = None
        if isinstance(dataOrNode, Node):
            item = dataOrNode
        else:
            item = Node(dataOrNode)

        if index == 0:
            item._next = self.head
            self.head = item
            self.length += 1
            return

        j = 0
        node = self.head
        prev = self.head
        while node._next and j < index:
            prev = node
            node = node._next
            j += 1

        if j == index:
            item._next = node
            prev._next = item
            self.length += 1

    def clear(self):
        """
        清空链表
        """
        self.head = None
        self.length = 0